package com.edu.leetcode.dataStruct;

/**
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * <p>
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * <p>
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @作者 five-five
 * @创建时间 2021/4/15
 */
public class Demo20 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(9);

        ListNode l4 = new ListNode(9);
        ListNode l5 = new ListNode(9, l4);
        ListNode l6 = new ListNode(9, l5);
        ListNode l7 = new ListNode(9, l6);
        ListNode l8 = new ListNode(9, l7);
        ListNode l9 = new ListNode(9, l8);
        ListNode l10 = new ListNode(9, l9);
        ListNode l11 = new ListNode(9, l10);
        ListNode l12 = new ListNode(9, l11);
        ListNode l13 = new ListNode(1, l12);
        Demo20 demo20 = new Demo20();
        ListNode listNode = demo20.addTwoNumbers(l1, l13);
        System.out.println(listNode);
        System.out.println(demo20.showListToInt(l13, 1, 0));
    }

    /**
     * @param l1 链表
     * @param l2 链表
     * @return 链表相加
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int i = this.showListToInt(l1, 1, 0);
        int j = this.showListToInt(l2, 1, 0);
        int result = i + j;
        String s = String.valueOf(result);
//        String reverseString = new StringBuilder(s).reverse().toString();
        //开始倒序制作链表
//        s=s.length()>9?s.substring(0,9):s;
        return makeListNodeInStringOrder(s);
    }

    /**
     * 根据string制作链表
     *
     * @param s
     * @return
     */
    private ListNode makeListNodeInStringOrder(String s) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int length = s.length();
        for (int i = length - 1; i >= 0; i--) {
            int val = Integer.parseInt(String.valueOf(s.charAt(i)));
            cur.next = new ListNode(val);
            cur = cur.next;
        }
        return pre.next;
    }


    /**
     * TODO: 2021/4/15 有一个bug没有解决，例如999999999可以正确计算，但是1999999999结果便不正确了，未解决
     *
     * @param listNode   链表
     * @param multiplier 乘数，默认从1开始
     * @param count      记录每一次递归的结果(初始化为0)
     * @return 返回 count
     */
    public int showListToInt(ListNode listNode, int multiplier, int count) {
        if (listNode == null) {
            return count;
        }
        count += listNode.val * multiplier;
        return showListToInt(listNode.next, multiplier * 10, count);
    }

}
